<?php
/**
 *  User：LRZ
 *  Date：2020/2/9
 *  Time：14:49
 */

/**
 *  67.二进制求和
 *
 *  标签：数学、字符串
 *
 *  给定两个二进制字符串，返回他们的和（用二进制表示）。
 *  输入为非空字符串且只包含数字 1 和 0。
 *
 *  示例 1:
 *      输入: a = "11", b = "1"
 *      输出: "100"
 *
 *  示例 2:
 *      输入: a = "1010", b = "1011"
 *      输出: "10101"
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/add-binary
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$a   = '1';
$b   = '111';
$res = addBinary($a, $b);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function addBinary($a, $b)
{
    $aLen = strlen($a);
    $bLen = strlen($b);
    if ($aLen > $bLen) {
        $b = str_pad($b, $aLen, '0', STR_PAD_LEFT);
    } elseif ($bLen > $aLen) {
        $a = str_pad($a, $bLen, '0', STR_PAD_LEFT);
    }

    for ($i = strlen($a) - 1; $i >= 0; $i--) {
        $a[$i] = (string)($a[$i] + $b[$i]);
        if ($a[$i] >= 2) {
            if ($i !== 0) {
                $a[$i]     = (string)($a[$i] % 2);
                $a[$i - 1] = (string)($a[$i - 1] + 1);
            } else {
                $a[$i] = (string)($a[$i] % 2);
                $a     = '1' . $a;
            }
        }
    }

    return $a;
}